﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BungieNode
{
    public class Node : IEnumerable<Node>
    {
        public Node Next { get; set; }
        public String Tag { get; set; }
        public Node Reference { get; set; }

        public Node()
        {
        }

        public Node(Node node)
        {
            Next = node.Next;
            Tag = node.Tag;
            Reference = node.Reference;
        }

        private bool IsTailNode
        {
            get { return Next == null; }
        }

        /// <summary>
        /// A duplicate copy of the list with no dependency on the original.
        /// O(n) time algorithm with O(1) additional space requirement
        /// </summary>
        /// <param name="list">A singly linked list that contains references to random nodes within the list</param>
        /// <returns></returns>
        public static Node DuplicateList(Node list)
        {
            if (list == null)
            {
                throw new ArgumentNullException("list");
            }

            //phase 1:
            //for each node in the list create a duplicate and insert it after the original node
            //precondition:  list = 1 -> i -> n -> null
            //postcondition: list = 1 -> 1Copy -> i -> iCopy -> n -> nCopy -> null
            Node node = list;
            while (node != null)
            {
                //create duplicate
                Node duplicate = new Node(node);
                //insert it after the original node
                node.Next = duplicate;
                //advance to the next original node (skip the duplicate node)
                node = node.Next.Next;
            }

            //save the start of the duplicate list
            Node duplicateHead = list.Next;

            //phase 2:
            //assign duplicates nodes to their respective duplicate references
            Node nodeDuplicate = duplicateHead;
            while (true)
            {
                //if the duplicate node has a reference then assign it from the original reference to the duplicate reference by advancing one position
                if(nodeDuplicate.Reference != null)
                {
                    nodeDuplicate.Reference = nodeDuplicate.Reference.Next;
                }
                //if the current position is the at the tail of the list then exit the loop
                if (nodeDuplicate.IsTailNode)
                {
                    break;
                }
                //advance to the next duplicate node
                nodeDuplicate = nodeDuplicate.Next.Next;
            }

            //phase 3: 
            //split the duplicates and originals into two lists
            //precondition:  list =  1 -> 1Copy -> i -> iCopy -> n -> nCopy -> null
            //               duplicateHead = 1Copy -> i -> iCopy -> n -> nCopy -> null
            //postcondition: list =  1 -> i -> n -> null
            //               duplicateHead = 1Copy -> iCopy -> nCopy -> null
            node = list;
            nodeDuplicate = duplicateHead;
            while (true)
            {
                //assign the orignal next by skipping the duplicate
                node.Next = node.Next.Next;
                //assign the duplicate next by skiping the original
                nodeDuplicate.Next = nodeDuplicate.Next.Next;

                //advance to the next original node
                node = node.Next;
                //advance to the next duplicate node
                nodeDuplicate = nodeDuplicate.Next;

                if (nodeDuplicate.IsTailNode)
                {
                    //change the orignal tail to point to null instead of the duplicate tail
                    //precondition: n -> nCopy
                    //postcondition: n -> null
                    node.Next = null;
                    break;
                }
            }

            //return the duplicate list
            return duplicateHead;
        }

        public IEnumerator<Node> GetEnumerator()
        {
            return new NodeEnumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}
